/**
 * Subsets with a unique sum.
 *
 * ANSWER: 115039000.
 */

#include <iostream>
#include <cassert>
#include <vector>
#include <numeric>
#include <utility>

static long long U(int k, const int B[], int n)
{
	assert(k*2 == n);
	assert(k < 64);

	// For each C(m,*), we use two 64-bit masks to store C(m,1), C(m,2), ...
	// The _exists_ mask corresponds to C(m,k) >= 1.
	// The _duplicate_ mask corresponds to C(m,k) >= 2.
	// The k-th bit (starting from zero) indicates C(m,k).
	typedef unsigned long long mask_t;
	struct three_state
	{
		mask_t exists;
		mask_t duplicate;
	public:
		three_state() : exists(0), duplicate(0) { }
	};

	int S = std::accumulate(B+0, B+n, 0);
	int M = (S-1)/2;
	std::vector<three_state> C(M+1);
	C[0].exists = 1;
	int max_m = 0;

	// Take each element from the set in turn, and updates the "exists"
	// and "duplicate" masks.
	for (int i = 0; i < n; i++)
	{
		int a = B[i];
		for (int m = std::min(max_m, M - a); m >= 0; --m)
		{
			if (C[m].exists)
			{
				C[m+a].duplicate |= (C[m+a].exists & (C[m].exists << 1));
				C[m+a].duplicate |= (C[m].duplicate << 1);
				C[m+a].exists |= (C[m].exists << 1);
			}
		}
		max_m = std::min(max_m + a, M);
	}

	// Count unique sums of k elements.
	int count = 0;
	for (int m = 1; m <= max_m; m++)
	{
		if ((C[m].exists ^ C[m].duplicate) & (1LL << k))
			++count;
	}

	return (long long)count * (long long)S;
}

void solve_problem_201()
{
#if 0
	int B[] = {1, 3, 6, 8, 10, 11};
	int k = 3;
#else
	int B[100];
	for (int i = 1; i <= 100; i++)
	{
		B[i-1] = i*i;
	}
	int k = 50;
#endif

	std::cout << U(k, B, sizeof(B)/sizeof(B[0])) << std::endl;
}
